package leetcode;

/***
 * 题目：264. 丑数 II
 * 链接：https://leetcode.cn/problems/ugly-number-ii/description/
 * 题解：动态规划
 */
public class NthUglyNumber {

    public static void main(String[] args) {
        System.out.println(nthUglyNumber(3));
    }
    public static int nthUglyNumber(int n) {
        if (n <= 0) return 0;
        int[] dp = new int[n];
        dp[0] = 1; // 第一个丑数是1
        int p2 = 0, p3 = 0, p5 = 0; // 初始化三个指针

        for (int i = 1; i < n; i++) {
            // 计算当前指针指向的丑数乘以对应因数的结果
            int next2 = dp[p2] * 2;
            int next3 = dp[p3] * 3;
            int next5 = dp[p5] * 5;

            // 选择最小值作为下一个丑数
            dp[i] = Math.min(next2, Math.min(next3, next5));

            // 更新指针：如果当前丑数由某指针生成，则该指针后移
            if (dp[i] == next2) p2++;
            if (dp[i] == next3) p3++;
            if (dp[i] == next5) p5++;
        }
        return dp[n - 1];
    }
}
